package demo1;

import java.util.Arrays;

/**
 * @Author liangzai
 * @Description:
 */
public class Training {
    public int jump(int[] nums) {
        int n = nums.length;
        int[] dp = new int[n];

        Arrays.fill(dp, Integer.MAX_VALUE-1);
        dp[n-1] = 0;

        for(int i=n-2; i>=0; i--){
            for(int j=1; j<=nums[i]; j++){
                if(i+j >= n) break;
                dp[i] = Math.min(dp[i], dp[i+j]+1);
            }
        }
        return dp[0];

    }

    public int countAsterisks(String s) {
        int count= 0;
        int sum=0;
        char[] charArray = s.toCharArray();
        for (char c : charArray) {
            if(c=='|'){
                count++;
            }
            if(count%2==0&&c=='*'){
                sum++;
            }
        }
        return sum;
    }

    public int respace(String[] dictionary, String sentence) {
        if(sentence==null||sentence.length()==0)
            return 0;
        int n=sentence.length();
        if(dictionary==null||dictionary.length==0)
            return n;
        int[] dp=new int[n+1];
        for(int i=1;i<=n;i++){
            dp[i]=dp[i-1]+1;
            for(String word:dictionary){
                int wlen=word.length();
                if(i-wlen>=0&&sentence.substring(i-wlen,i).equals(word)){
                    dp[i]=Math.min(dp[i-wlen],dp[i]);
                }
            }
        }
        return dp[n];
    }
}
